<html>
<head>
  <title>Manifold learning</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="853"/>
<h1>Manifold learning</h1>

<div>
<span><div><div><span>    <span>    </span></span>Manifold learning is an approach to <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>non-linear dimensionality reduction</b></font>. Algorithms for this task are based on the idea that the <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>dimensionality of many data sets</b></font> is only <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>artificially high</b></font>.</div><div><img src="Manifold learning_files/Image.png" type="image/png" data-filename="Image.png" style="width: 900.0px; height: 480.0px;"/></div><div><font style="font-size: 24pt; color: rgb(50, 135, 18);"><b>理解：上图显示了，三维的数据集转化为了二维数据集，确实损失了一些信息，但可以有选择的保留重要的信息</b></font></div><div><br/></div><h2><font style="font-size: 18pt; font-weight: normal; color: rgb(28, 51, 135);"><br/></font></h2><h2><font style="font-size: 18pt; font-weight: normal; color: rgb(28, 51, 135);">Introduction</font></h2><div>High-dimensional datasets can be very difficult to visualize.</div><div>The simplest way to accomplish this dimensionality reduction is by <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>taking a random projection of the data</b></font>.</div><div><span style="-en-paragraph: true;">In a random projection, it is likely that the more interesting structure within the data will be lost.</span></div><div style="text-align: center;"><a href="http://scikit-learn.org/stable/auto_examples/manifold/plot_lle_digits.html"><img src="Manifold learning_files/Image [1].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></a> <a href="http://scikit-learn.org/stable/auto_examples/manifold/plot_lle_digits.html"><img src="Manifold learning_files/Image [2].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></a></div><div><br/></div><div><span>    <span>    </span></span>a number of supervised and unsupervised linear dimensionality reduction frameworks have been designed, s<font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>uch as Principal Component Analysis (PCA), Independent Component Analysis, Linear Discriminant Analysis,</b></font> and others. These algorithms <b>define specific rubrics</b> to choose an “interesting” linear projection of the data. These methods can be powerful, but often miss important non-linear structure in the data</div><div><br/></div><div><span>    <span>    </span></span>Manifold Learning can be thought of as an attempt to generalize linear frameworks like PCA to be sensitive to non-linear structure in data. Though supervised variants exist, the typical manifold learning problem is unsupervised: <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>it learns the high-dimensional structure of the data from the data itself, without the use of predetermined classifications</b></font>.</div><div><br/></div><h2><font style="font-size: 18pt; font-weight: normal; color: rgb(28, 51, 135);">Isomap</font></h2><div style="text-align: left;"><span>    <span>    </span></span>Isomap seeks a lower-dimensional embedding which maintains geodesic distances between all points.<br/></div><div style="text-align: center;"><img src="Manifold learning_files/Image [3].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></div><div><span style="-en-paragraph: true;">The Isomap algorithm comprises three stages:</span></div><ol><li><span style="font-weight: bold;">Nearest neighbor search.</span> Isomap uses <a href="http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTree" title="sklearn.neighbors.BallTree">sklearn.neighbors.BallTree</a> for efficient neighbor search. The cost is approximately <img src="Manifold learning_files/Image [4].png" type="image/png" data-filename="Image.png"/>, for <img src="Manifold learning_files/Image [5].png" type="image/png" data-filename="Image.png"/> nearest neighbors of <img src="Manifold learning_files/Image [6].png" type="image/png" data-filename="Image.png"/> points in <img src="Manifold learning_files/Image [7].png" type="image/png" data-filename="Image.png"/> dimensions.</li><li><span style="font-weight: bold;">Shortest-path graph search.</span> The most efficient known algorithms for this are <span style="font-style: italic;">Dijkstra’s Algorithm</span>, which is approximately <img src="Manifold learning_files/Image [8].png" type="image/png" data-filename="Image.png"/>, or the <span style="font-style: italic;">Floyd-Warshall algorithm</span>, which is <img src="Manifold learning_files/Image [9].png" type="image/png" data-filename="Image.png"/>. The algorithm can be selected by the user with the path_method keyword of Isomap. If unspecified, the code attempts to choose the best algorithm for the input data.</li><li><span style="font-weight: bold;">Partial eigenvalue decomposition.</span> The embedding is encoded in the eigenvectors corresponding to the <img src="http://scikit-learn.org/stable/_images/math/b9d10b54744d07746b97f53c55eb98046fd76c8c.png"></img> largest eigenvalues of the <img src="Manifold learning_files/Image [10].png" type="image/png" data-filename="Image.png"/> isomap kernel. For a dense solver, the cost is approximately <img src="Manifold learning_files/Image [11].png" type="image/png" data-filename="Image.png"/>. This cost can often be improved using the ARPACK solver. The eigensolver can be specified by the user with the path_method keyword of Isomap. If unspecified, the code attempts to choose the best algorithm for the input data.</li></ol><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">The overall complexity of Isomap is</span> <img src="Manifold learning_files/Image [12].png" type="image/png" data-filename="Image.png"/><span style="-en-paragraph: true;">.</span></div><ul><li><img src="Manifold learning_files/Image [13].png" type="image/png" data-filename="Image.png"/> : number of training data points</li><li><img src="Manifold learning_files/Image [14].png" type="image/png" data-filename="Image.png"/> : input dimension</li><li><img src="Manifold learning_files/Image [15].png" type="image/png" data-filename="Image.png"/> : number of nearest neighbors</li><li><img src="http://scikit-learn.org/stable/_images/math/b9d10b54744d07746b97f53c55eb98046fd76c8c.png"></img> : output dimension</li></ul><div><br/></div><h2><font style="font-size: 18pt; font-weight: normal; color: rgb(28, 51, 135);">Locally Linear Embedding</font></h2><div><span>    <span>    </span></span>seeks a lower-dimensional projection of the data which preserves distances within local neighborhoods. It can be thought of as a series of local Principal Component Analyses which are globally compared to find the best non-linear embedding.</div><div><br/></div><div style="text-align: center;"><img src="Manifold learning_files/Image [16].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></div><h2><font style="font-size: 18pt; font-weight: normal; color: rgb(28, 51, 135);">Modified Locally Linear Embedding</font></h2><div><img src="Manifold learning_files/Image [17].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></div><h2><font style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Hessian Eigenmapping</font></h2><div><img src="Manifold learning_files/Image [18].png" type="image/png" data-filename="Image.png" style="width: 320.0px; height: 240.0px;"/></div><div><br/></div><div><br/></div></div></span>
</div></body></html> 